package com.suanfa.node;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 两个数结构，一个是否包含另外一个树
 */
public class SameNode {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        TreeNode treeNode11 = new TreeNode(2);
        TreeNode treeNode12 = new TreeNode(3);
        TreeNode treeNode111 = new TreeNode(4);
        TreeNode treeNode112 = new TreeNode(5);
        TreeNode treeNode121 = new TreeNode(6);

        TreeNode treeNode0 = new TreeNode(12);
        treeNode.left = treeNode11;
        treeNode.right = treeNode12;
        treeNode11.left = treeNode111;
        treeNode11.right = treeNode112;
        treeNode12.left = treeNode121;

        //System.out.println(dfs(treeNode, treeNode0));
        preOrder(treeNode, 1);
        System.out.println("/************************/");
        inOrder(treeNode, 1);
        System.out.println("/************************/");
        poseOrder(treeNode, 1);
    }


    public static boolean dfs(TreeNode root, TreeNode sub) {

        if (root == null) {
            return false;
        }

        return check(root, sub) || dfs(root.left, sub) || dfs(root.right, sub);

    }

    public static boolean check(TreeNode root, TreeNode sub) {
        if (root == null && sub == null) {
            return true;
        }
        if (root == null || sub == null || root.val != sub.val) {
            return false;
        }
        return check(root.left, sub.left) && check(root.right, sub.right);
    }


    public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
        List<Integer> sub = new ArrayList<>();
        getNodeArr(sub, subRoot);

        TreeNode td = readNode(root, subRoot);
        while (td != null) {
            List<Integer> r = new ArrayList<>();
            getNodeArr(r, td);
            int[] su = sub.stream().mapToInt(Integer::valueOf).toArray();
            int[] rr = r.stream().mapToInt(Integer::valueOf).toArray();
            boolean b = Arrays.equals(su, rr);
            if (!b) {
                td = readNode(td, subRoot);
            } else {
                return b;
            }
        }
        return false;
    }


    public static TreeNode readNode(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return null;
        }
        if (root.val == subRoot.val) {
            return root;
        }
        TreeNode tr = readNode(root.left, subRoot);
        if (tr != null) {
            return tr;
        }
        TreeNode tl = readNode(root.right, subRoot);
        if (tl != null) {
            return tl;
        }
        return null;
    }


    public static void getNodeArr(List<Integer> list, TreeNode node) {
        if (node == null) {
            return;
        }
        list.add(node.val);
        getNodeArr(list, node.left);
        getNodeArr(list, node.right);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    static void preOrder(TreeNode node, int count) {
        if (node == null) {
            return;
        }
        System.out.println(count + "层:" + node.val);
        count ++;
        preOrder(node.left, count);
        preOrder(node.right, count);
    }

    static void inOrder(TreeNode node, int count) {
        if (node == null) {
            return;
        }
        inOrder(node.left, count + 1);
        System.out.println(count + "层:" + node.val);
        inOrder(node.right,  count + 1);
    }

    static void poseOrder(TreeNode node, int count) {
        if (node == null) {
            return;
        }
        poseOrder(node.left, count + 1);
        poseOrder(node.right,  count + 1);
        System.out.println(count + "层:" + node.val);
    }

}
